Computers have transformed the way that we access data, process information, and communicate. For instance, computing systems may be used to represent and utilize even complex equations and other symbolic representations. Such equations may represent physical algebraic equations, logic programming, commutating systems, and physical, chemical and biological systems.
Before fully applying an equation, it is desirable transform an equation or other symbolic representation. One transformation is the reduction of an equation. Another transformation is a “reaction” as represented in biological simulations or workflow. The following identities (1) through (6) each represent a relative simple well-known algebraic identity where Y is the algebraic variable and will be subsequently used to describe an algebraic equation reduction operation:Y×0=0  (1)Y×1=Y  (2)Y+0=Y  (3)Y+−Y=0  (4)Y×(1/Y)=1  (5)Y×Y=Y^2  (6)The identities hold true for every value of Y, except equation (5), which is valid at all values of Y except for zero. Other identities exist for logic programming, commutating systems, and physical, chemical and biological systems.
As previously mentioned, identities may be used to simplify or otherwise transform an equation. For instance, consider the following algebraic equation (7).Z=(A×1)+(B+0)+−(A+0)+(C×0)+−C+A−1+(D×(1/D))+A+−B  (7)
Applying identity (1) to equation (7) yields the following simplified form of equation (7) as equation (8).Z=(A×1)+(B+0)+−(A+0)+0+−C+A−1+(D×(1/D))+A+−B  (8)
Applying identity (2) to equation (8) yields the following simplified form of equation (8) presented as equation (9):Z=A+(B+0)+−(A+0)+0+−C+A−1+(D×(1/D))+A+−B  (9)
Applying identity (3) to equation (9) yields the following simplified form of equation (9) presented as equation (10):Z=A+B+−A+−C+A−1+(D×(1/D))+A+−B  (10)
Applying identity (4) to equation (10) yields the following simplified form of equation (10) presented as equation (11):Z=−C+A−1+(D×(1/D))+A  (11)
Applying identity (5) to equation (11) yields the following simplified form of equation (11) presented as equation (12):Z=−C+A−1+1+A  (12)
Applying identity (4) once again yields equation (13) as follows:Z=−C+A+A  (13)
Which may be rewritten as equation 14:Z=−C+2A  (14)
Thus, the application of identities may go far to reduce equations into simpler, more manageable forms. Identities may also be used to perform other transformations on either equations or other symbolic representations.
Computing systems may perform these types of equation reductions in order to simplify processing associated with applying the equation. While the reductions shown above with respect to equations (7) through (14) involve just a dozen or so terms, computing systems may efficiently process equations involving many millions of terms. Nevertheless, there can be significant savings in processing time when computer-representations of equations are reduced to simpler forms, even if those simpler forms still involve many millions of terms.
One structure used to represent a side of an identity is referred to in the art as a “match”. FIG. 1A illustrates a match that represents the identity of equation (1). Matches are generally structured as a hierarchical tree, with parent nodes representing operators that join or apply to descendent terms represented by descendent branches in a particular manner defined by the operator. FIGS. 1B through 1F each illustrate a match that represents the identity of respective equations (2) through (6). Similar matches are used to represent non-algebraic equations as well. In FIGS. 1A through 1F, some operators are Associative Commutative (AC) and others are not. For instance, plus “+”, and times “×” are AC operators, whereas minus “−”, reciprocal “÷”, and exponent “^” are not AC operators.
There are several types of identities, linear identities and non-linear identities. A linear identity is an identity in which each side of the equation has just one occurrence of each variable. A non-linear identity is an identity in which at least one side has at least one variable that occurs multiple times. For instance, referring to FIGS. 1A through 1C, the only variable in the match (i.e., Y) occurs only once (at most) on each side of the equation. Thus, the identities represented by FIGS. 1A through 1C are linear identities. On the other hand, the variable (i.e., Y) occurs twice on the left-hand side of the identities of FIGS. 1D and 1E. Thus, the identities represented by FIGS. 1D and 1E are non-linear.
Matches may be used to represent identities for non-algebraic equations as well. For example, FIG. 2 shows a match for one side of an equation for a sequent calculus definition of propositional logic. In this match the comma (,) is an associative commutative context operator. The two other operators in the pattern below are implies (→) and Atom. G, P, and C are variables. G and C occur only once while P occurs twice which constrains the binding of the pattern to the subject. The constraint is indicated by the dotted line. P is referred to as the reaction variable in this kind of match. The match of FIG. 2 represents the proposition of propositional logic that if a first fact (along with any other information) is known, and the first fact implies a second fact, then the second fact is also known.
FIG. 3 shows a match for one side of an equation used in Pi calculus communicating process interact with channels. In the theory, par (|) and alternative (+) are Associative Commutative (AC) operators. Sequence (.) and bar (_) are regular operators. The reaction variable in FIG. 3 is “a”. The others variables are only used once.
FIG. 4 shows a match for one side of an equation used in the Phago reaction of Brane calculus (refer to Article by Luca Calculi entitled Interactions of Biological Membranes, which is cited by the Applicant) used to represent biological systems. In this theory, the system and membrane composition operators (o and |) are AC operators. The reaction variable is n.
Linear identities may be easily applied to reduce equations using fast algorithms. Non-linear identities are, on the other hand, NP hard. Accordingly, it can be quite computationally intensive to apply non-linear identities to reduce equations.